﻿#include <iostream>
#include "../Matrix/Matrix.h"

static const int M[] = {
    1, 1, 
    1, 0,
};

static int fibonacci(int n)
{
    if (n == 0) return 1;
    if (n == 1) return 1;

    int f1_0[] = {
        1, 1,
    };

    int* m = powMatrix(M, 2, 2, n - 1);
    int* resM = multiMatrix(f1_0, 1, 2, m, 2, 2);
    int res = resM[0];
    free(resM);
    free(m);
    return res;
}

// 使用矩阵计算斐波那契数列
// F(0)=1
// F(1)=1
// F(2)=F(0)+F(1)
// ...
// F(n)=F(n-1)+F(n-2)
//                                  a,b
// [F(n),F(n-1)] = [F(n-1),F(n-2)]*[   ]
//                                  c,d
// [F(2),F(1)] = [F(1),F(0)]*M
// [F(3),F(2)] = [F(2),F(1)]*M=[F(1),F(0)]*M^2
//...
// [F(n),F(n-1)] = [F(1),F(0)]*M^(n-1)
int main_Fibonacci()
{
    for (int n = 2; n <= 20; n++)
    {
        printf("F[%d]=%d\n", n, fibonacci(n));
    }

    return 0;
}